package com.mamingchao.foundation.QuestionPool;

import java.util.HashMap;
import java.util.Map;

/**
 * 暴力枚举，O(N的平方)
 *
 * 在给定数组里面找到 两数相加等于 target的数
 *
 * Created by mamingchao on 2020/11/14.
 */
public class AddSum {

    public static void main(String[] args) {
        int[] temp = new int[]{1,10,8,5,4,6,3,2,7,16};

        twoSum1(temp,9);
        twoSum(temp,9);
    }

    /**
     * 暴力递归，这个时间复杂度 高
     * O(N*N)
     * @param arr
     */
    private static void twoSum1(int[] arr, int target){
        boolean flag = false;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > 9)
                continue;
            for (int j = i+1; j < arr.length; j++) {
                if (arr[i] + arr[j] == 9) {
                    System.out.println(i + "^"+ arr[i] +  "--" + j + "^"+ arr[j]);
                    flag = true;
                    break;
                }
            }

            if (flag)
                break;
        }
    }

    /**
     * 上面的暴力递归，复杂就复杂在 里面那层递归上
     * 下面这种快，主要是因为 不再用数组递归的方式，用链表或者红黑树 连实现快速查找 是否存在 target - nums[i] 这个元素
     * 时间复杂度 o(N)，N是数组的元素数量，对于每一个元素x，我们可以O(1)的查找 target -x
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                System.out.println(hashtable.get(target - nums[i]) +  "--" + i);
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }


}
